package algorithm.niuke;

import java.util.ArrayList;
import java.util.List;

public class E太平洋大西洋水流问题 {
    /*
     * 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
     * 
     * 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
     * 
     * 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
     * 
     * 
     * 
     * 提示：
     * 
     * 输出坐标的顺序不重要 m 和 n 都小于150
     * 
     * 
     * 示例：
     * 
     * 
     * 
     * 给定下面的 5x5 矩阵:
     * 
     * 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7)
     * 1 4 5 * ~ (5) 1 1 2 4 * * * * * *大西洋
     * 
     * 返回:
     * 
     * [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
     */
    public List<int[]> pacificAtlantic(int[][] matrix) {
        // 上下左右中有一个点能流入太平洋，当前点比那个点海拔高，那么这个点也能流入太平洋,太平洋同理
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] pacific = new int[row + 2][col + 2];// 太平洋
        int[][] atlantic = new int[row + 2][col + 2];// 大西洋
        map = matrix;
        for (int i = 0; i < row; i++) {
            dfs(pacific, row, col, i, 0);
            dfs(atlantic, row, col, i, col - 1);
        }
        for (int j = 0; j < col; j++) {
            dfs(pacific, row, col, 0, j);
            dfs(atlantic, row, col, row - 1, j);
        }

        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (pacific[i][j] == 1 && atlantic[i][j] == 1) {
                    int[] temp = { i, j };
                    res.add(temp);
                }
            }
        }
        return res;
    }

    int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    int[][] map = null;

    void dfs(int[][] ocean, int row, int col, int i, int j) {
        if (!valid(row, col, i, j)) {
            return;
        }
        if (ocean[i][j] == 1) {
            return;
        }
        ocean[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int ni = dir[k][0] + i;
            int nj = dir[k][1] + j;
            if (valid(row, col, ni, nj) && map[i][j] <= map[ni][nj]) {
                dfs(ocean, row, col, ni, nj);
            }
        }
    }

    boolean valid(int row, int col, int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        return true;
    }
}
